Paper 2013/356

Verifying Computations with State (Extended Version)

Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish

Abstract

When a client outsources a job to a third party (e.g., the cloud), how can the client check the result, without reexecuting the computation? Recent work in _proof-based verifiable computation_ has made significant progress on this problem by incorporating deep results from complexity theory and cryptography into built systems. However, these systems work within a stateless model: they exclude computations that interact with RAM or a disk, or for which the client does not have the full input. This paper describes Pantry, a built system that overcomes these limitations. Pantry composes proof-based verifiable computation with untrusted storage: the client expresses its computation in terms of digests that attest to state, and verifiably outsources _that_ computation. Using Pantry, we extend verifiability to MapReduce jobs, simple database queries, and interactions with private state. Thus, Pantry takes another step toward practical proof-based verifiable computation for realistic applications.

Note: Minor edits

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. ACM Symposium on Operating Systems Principles (SOSP)
DOI
10.1145/2517349.2522733
Keywords
ryptographic protocolsimplementationapplications of PCPszero knowledgeverifiable computation with state
Contact author(s)
pepper @ cs utexas edu
History
2013-11-14: last of 3 revisions
2013-06-10: received
See all versions
Short URL
https://ia.cr/2013/356
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/356,
      author = {Benjamin Braun and Ariel J.  Feldman and Zuocheng Ren and Srinath Setty and Andrew J.  Blumberg and Michael Walfish},
      title = {Verifying Computations with State (Extended Version)},
      howpublished = {Cryptology {ePrint} Archive, Paper 2013/356},
      year = {2013},
      doi = {10.1145/2517349.2522733},
      url = {https://eprint.iacr.org/2013/356}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.